var Utils = require('geoUtils');

/**
 * createMap函数将返回这样的数据类型的二维数组
 * @param {*} item 
 * @param {*} canSelect 
 * @param {*} directions //此数据将在选择路径时再赋值    createMap时不进行赋值
 */
function MapInformation(item, canSelect, position, directions) {
    this.item = item;
    this.canSelect = canSelect;
    this.position = position;
    this.directions = directions;
}

var MapUtils = {
    DirectionEnum: {
        UP: { x: -1, y: 0 },
        DOWN: { x: 1, y: 0 },
        LEFT: { x: 0, y: -1 },
        RIGHT: { x: 0, y: 1 },
        UPPER_LEFT: { x: -1, y: -1 },
        UPPER_RIGHT: { x: -1, y: 1 },
        LOWER_LEFT: { x: 1, y: -1 },
        LOWER_RIGHT: { x: 1, y: 1 },
    },
    /**
     * 根据给定的道具集合，创建二维数据集
     * @param {*} items 道具集合（1维）
     * @param {*} numVols 行数
     * @param {*} numCols 列数
     * @returns 返回包装了items的二维数据集，用于搜索功能。
     */
    createMap(items, numVols, numCols) {
        //将要返回的对象
        var ret = {
            //用于探索的二维数组
            array: [],
            //用于记录步数不足maxSteps的item的数组
            notEnough: [],
        };

        //记录数组items当前位置的变量
        var index = 0;

        for (var i = 0; i < numVols; i++) {
            ret.array.push([]);
            for (var j = 0; j < numCols; j++) {
                //获得item  同时index更新
                var item = items[index++];

                var mapObj = new MapInformation(item, true, { x: i, y: j });

                ret.array[i].push(mapObj);
            }
        }
        return ret;
    },
    /**
     * 
     * @param {*} map createMap函数返回的对象
     * @param {*} directions 可以选择的方向
     * @param {*} maxSteps 想要走几步
     * @param {*} useStrict 当步数不足maxSteps时是否返回选到的其它的最大步数
     * @param {*} start 起点对象数组[{col:0,vol:0},{col:1,vol:1}]
     * @example
     * var result = MapUtils.serachMap(map, 
        *  [MapUtils.DirectionEnum.up, MapUtils.DirectionEnum.down],
        *  2, true);
        */
    searchMap(map, directions, maxSteps, useStrict, start) {
        var mapObjArray = this._localSearchMap(map, directions, maxSteps, useStrict, start);
        var itemArray = this._mapObjArrayToItemArray(mapObjArray);
        return itemArray;
    },
    /**
     * 
     * @param {*} map 
     * @param {*} PreinstallObjs [{directions:dir,maxSteps:num,useStrict,start:{}},{directions:dir,maxSteps:num,start:{}}]
     */
    searchMapByPreinstall(map, PreinstallObjs) {
        var pObj = Utils.array.random(PreinstallObjs, 1, true)[0];
        return this.searchMap(map, pObj.directions, pObj.maxSteps, pObj.useStrict, pObj.start);

    },
    /**
     * 
     * @param {*} map createMap函数返回的对象
     * @param {*} directions 可以选择的方向
     * @param {*} maxSteps 想要走几步
     * @param {*} useStrict 当步数不足maxSteps时是否返回选到的其它的最大步数
     * @example
     * var result = MapUtils.serachMap(map, 
     *  [MapUtils.DirectionEnum.up, MapUtils.DirectionEnum.down],
     *  2, true);
     */
    _localSearchMap(map, directions, maxSteps, useStrict, start) {
        var ret = [];
        //记录本次便利未达到指定步数的路线
        var notEnough = [];
        //用于判断item的栈
        var storehouse = new Array(maxSteps);
        //栈指针 指向栈顶元素
        var s = -1;
        //用于记录当前已经选择的mapObj的数组
        var selectMapObj = [];

        //添加可选择的方向
        this._addDirections(map.array, directions);

        var canSelectMapObjs = this._getCanSelectObj(map.array, start);
        do {
            //每次循环前清空数组
            selectMapObj = [];

            //回复数据记录
            this._recoverNotEnough(notEnough);
            this._addDirections(notEnough, directions);
            // notEnough = [];
            //选择第一个节点
            var firstMapObj = this._selectFirstObj(canSelectMapObjs);
            if (firstMapObj == false)
                break;
            //入栈
            storehouse[++s] = firstMapObj;
            //加入选择队列
            selectMapObj.push(firstMapObj);

            var lastMapObj = firstMapObj;
            for (var i = 0; i < maxSteps - 1; i++) {
                lastMapObj = this._selectNextObj(map.array, lastMapObj);
                if (lastMapObj != null) {
                    //入栈
                    storehouse[++s] = lastMapObj;
                    //加入选择队列
                    selectMapObj.push(lastMapObj);
                }
                else {
                    //栈内元素为空本次寻找结束  将当前记录的item数组添加到notEnough中
                    if (--s < 0) {
                        notEnough.push(selectMapObj);

                        break;
                    }
                    //栈不为空 栈顶元素出栈 新的栈顶元素继续寻找
                    lastMapObj = storehouse[s];

                    //本次未选到mapObj  i-- 保证总量达到maxSteps
                    i--;
                }
            }
            if (selectMapObj.length == maxSteps) {
                ret = selectMapObj;
                break;
            }
        } while (canSelectMapObjs.length > 0);
        if (ret.length == 0 && useStrict == true) {
            ret = this._findLongestArrayInNotEnough(notEnough);
        }
        this._recoverNotEnough(notEnough);
        return ret;


    },
    /**
     * 撤销本次查找的不足路线的canSelect
     * @param {*} notEnough 
     */
    _recoverNotEnough(notEnough) {
        notEnough.forEach(notEnoughArray => {
            notEnoughArray.forEach(element => {
                element.canSelect = true;
            });
        });
    },

    /**
     * 添加方向
     * @param {*} mapArray 
     * @param {*} directions 
     */
    _addDirections(mapArray, directions) {
        mapArray.forEach(mapObjArray => {
            mapObjArray.forEach(mapIns => {
                mapIns.directions = directions.concat();
            });
        });
    },
    /**
     * 获得map中可以选择的所有mapObj
     * @param {*} mapArray 
     */
    _getCanSelectObj(mapArray, start) {
        //获得可选择的obj
        var ret = [];
        if (start == null) {
            var numVols = mapArray.length;
            var numCols = mapArray[0].length;
            for (var i = 0; i < numVols; i++) {
                for (var j = 0; j < numCols; j++) {
                    var mapObj = mapArray[i][j];
                    if (mapObj.canSelect == true) {
                        ret.push(mapObj);
                    }
                }
            }
        }
        else {
            var mapObj = mapArray[start.col][start.vol];
            if (mapObj.canSelect == true) {
                ret.push(mapObj);
            }

        }
        return ret;
    },
    /**
     * 随机选择一个item为初始节点
     * @param {*} canSelectMapObjs 
     */
    _selectFirstObj(canSelectMapObjs) {
        if (canSelectMapObjs.length == 0)
            return false;
        var firstMapObj = Utils.array.random(canSelectMapObjs, 1, true)[0];
        firstMapObj.canSelect = false;
        return firstMapObj;
    },
    /**
     * 根据lastMapObj中记录的directions选择下一个mapObj选择失败返回null
     * @param {*} mapArray 
     * @param {*} lastMapObj 
     */
    _selectNextObj(mapArray, lastMapObj) {
        for (var i = 0; i < lastMapObj.directions.length;) {
            //随机选择一个方向并且删除使用过的方向
            var d = Utils.array.random(lastMapObj.directions, 1, true)[0];

            var nextX = lastMapObj.position.x + d.x;
            var nextY = lastMapObj.position.y + d.y;
            //判断是否出界
            if (nextX >= 0 && nextY >= 0 && nextX < mapArray.length && nextY < mapArray[0].length) {
                var mapObj = mapArray[nextX][nextY];
                //判断是否可选
                if (mapObj.canSelect == true) {
                    mapObj.canSelect = false;
                    //删除来时的方向
                    this._removeDirection(mapObj.directions, { x: -d.x, y: -d.y });
                    return mapObj;
                }
            }

        }
        return null;
    },
    /**
     * 第一个参数是对象数组objArray
     * 第二个参数是自己定义的对象obj
     * 删除对象数组中属性值等于obj中的属性值的对象
     * 例如    objArray[{a:1,b:1,c:1},{a:1,b:2,c:1}]
     *         obj{b:1}
     * 函数运行完毕后objArray[{a:1,b:2,c:1}]
     * @param {*} directions 
     * @param {*} dir 
     */
    _removeDirection(directions, dir) {
        for (var i = 0; i < directions.length; i++) {
            var element = directions[i];
            var isRemove = true;
            for (var attr in dir) {
                if (element[attr] != dir[attr]) {
                    isRemove = false;
                    break;
                }
            }
            if (isRemove) {
                directions.splice(i, 1);
                return true;
            }

        }

    },
    /**
     * 返回notEnough数组中的最长的一项
     * @param {*} notEnough 
     */
    _findLongestArrayInNotEnough(notEnough) {
        var ret = [];
        for (var i = 0; i < notEnough.length; i++) {
            if (notEnough[i].length > ret.length) {
                ret = notEnough[i];
            }
        }
        Utils.array.remove(notEnough, ret);
        return ret;
    },

    _mapObjArrayToItemArray(mapObjArray) {
        var ret = [];
        mapObjArray.forEach(element => {
            ret.push(element.item);
        });
        return ret;
    },
};

module.exports = MapUtils;